Column generation for a multitrip vehicle routing problem with time windows, driver work hours, and heterogeneous fleet

摘要

This study addresses a vehicle routing problem with time windows, accessibility restrictions on customers, and a fleet that is\udheterogeneous with regard to capacity and average speed. A vehicle can performmultiple routes per day, all starting and ending at a\udsingle depot, and it is assigned to a single driverwhose totalwork hours are limited.Acolumn generation algorithmis proposed.The\udcolumn generation pricing subproblem requires a specific elementary shortest path problem with resource constraints algorithm\udto address the possibility for each vehicle performingmultiple routes per day and to address the need to set the workday’s start time\udwithin the planning horizon. A constructive heuristic and a metaheuristic based on tabu search are also developed to find good\udsolutions.